#!/usr/bin/env python
# -*- coding: utf-8 -*-
# 
# Copyright (c) 2017 Baidu.com, Inc. All Rights Reserved
# 

"""
File: run4.py
Author: zhangyang(zhangyang40@baidu.com)
Date: 2018/1/5 0005 11:30
"""
"""
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。
n<=39
"""


class Solution:
    def Fibonacci(self, n):
        if n <= 1:
            return n
        record = []
        record[0] = 0
        record[1] = 1
        for i in range(2, n + 1):
            record[i] = record[i - 1] + record[i - 2]
        return record[n]
